package com.fanshuai.algorithms.dynamic;

/**
 * 凑零钱问题：
 * 给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，
 * 问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
 *
 * 实现方式为：递归实现、回溯法实现、动态规划实现
 */
public class Coin {
    /**
     * 递归实现
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange(int[] coins, int amount) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }

        int minCoin = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subMin = coinChange(coins, amount - coin);
            if (subMin == -1) {
                continue;
            }
            if (subMin < minCoin) {
                minCoin = subMin;
            }
        }
        if (minCoin == Integer.MAX_VALUE) {
            return -1;
        }
        return minCoin + 1;
    }

    /**
     * 递归实现  通过dp table记录子问题的解，防止重复递归求解。此方法实际上是动态规划法，为自顶向下的方法
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange2(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;

        return coinChange0(coins, amount, dp);
    }

    private static int coinChange0(int[] coins, int amount, int[] dp) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        if (dp[amount] > 0) {
            return dp[amount];
        }

        int minCoin = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subMin = coinChange0(coins, amount - coin, dp);
            if (subMin == -1) {
                continue;
            }
            if (subMin < minCoin) {
                minCoin = subMin;
            }
        }
        if (minCoin == Integer.MAX_VALUE) {
            dp[amount] = -1;
        } else {
            dp[amount] = minCoin + 1;
        }
        return dp[amount];
    }

    /**
     * 硬币问题，动态规划解法
     * dp table: dp[N] = min{1+dp[N-coin]}, 对任意coin属于coins
     * bad case: dp[0]=0, dp[N]=-1,对任意N<0
     * 状态转移方程：
     * @param coins
     * @param amount
     * @return
     */
    private static int coinChangeDP(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin < 0) {
                    continue;
                }
                if (dp[i - coin] + 1 < dp[i]) {
                    dp[i] = dp[i - coin] + 1;
                }
            }
        }
        for (int i = 1; i < dp.length; i++) {
            if (dp[i] == Integer.MAX_VALUE) {
                dp[i] = -1;
            }
        }

        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};

        int[] amounts = {11, 3, 6, 7, 23};
        //动态规划
        for (int amount : amounts) {
            System.out.println(coinChangeDP(coins, amount));
        }

        //递归
        for (int amount : amounts) {
            System.out.println(coinChange(coins, amount));
        }

        //带备忘录dp table的递归
        for (int amount : amounts) {
            System.out.println(coinChange2(coins, amount));
        }
    }

}
